Approximation Algorithms for Minimum PCR Primer Set Selection with Amplification Length and Uniqueness Constraints

摘要

A critical problem in the emerging high-throughput genotyping protocols is tominimize the number of polymerase chain reaction (PCR) primers required toamplify the single nucleotide polymorphism loci of interest. In this paper westudy PCR primer set selection with amplification length and uniquenessconstraints from both theoretical and practical perspectives. We give a greedyalgorithm that achieves a logarithmic approximation factor for the problem ofminimizing the number of primers subject to a given upperbound on the length ofPCR amplification products. We also give, using randomized rounding, the firstnon-trivial approximation algorithm for a version of the problem that requiresunique amplification of each amplification target. Empirical results onrandomly generated testcases as well as testcases extracted from the from theNational Center for Biotechnology Information's genomic databases show that ouralgorithms are highly scalable and produce better results compared to previousheuristics.